Largest perimeter triangle

Time: O(NLogN); Space: O(1); easy

Given an array A of positive lengths, return the largest perimeter of a triangle with non-zero area, formed from 3 of these lengths.

If it is impossible to form any triangle of non-zero area, return 0.

Example 1:

Input: A = [2,1,2]

Output: 5

Example 2:

Input: A = [1,2,1]

Output: 0

Example 3:

Input: A = [3,2,3,4]

Output: 10

Example 4:

Input: A = [3,6,2,3]

Output: 8

Constraints:

• 3 <= len(A) <= 10000

• 1 <= A[i] <= 10^6

1. Sort

Intuition

Without loss of generality, say the sidelengths of the triangle are a <= b <= c. The necessary and sufficient condition for these lengths to form a triangle of non-zero area is a + b > c.

Say we knew cc already. There is no reason not to choose the largest possible aa and bb from the array. If a + b > >c, then it forms a triangle, otherwise it doesn’t.

Algorithm

This leads to a simple algorithm: Sort the array. For any cc in the array, we choose the largest possible a <= b <= c: these are just the two values adjacent to c. If this forms a triangle, we return the answer.

class Solution1(object):
    """
    Time: O(NLogN), where N is the length of A.
    Space: O(1).
    """
    def largestPerimeter(self, A) -> int:
        """
        :type A: List[int]
        :rtype: int
        """
        A.sort()
        # for i in reversed(range(len(A) - 2)):
        for i in range(len(A) - 3, -1, -1):
            if A[i] + A[i+1] > A[i+2]:
                return A[i] + A[i+1] + A[i+2]
        return 0

s = Solution1()
A = [2,1,2]
assert s.largestPerimeter(A) == 5
A = [1,2,1]
assert s.largestPerimeter(A) == 0
A = [3,2,3,4]
assert s.largestPerimeter(A) == 10
A = [3,6,2,3]
assert s.largestPerimeter(A) == 8

See also:

https://leetcode.com/problems/largest-perimeter-triangle